package 分治.归并排序;

class Solution {
    int [] tmp;
    //  int ret;
    public int reversePairs(int[] nums) {

        int n = nums.length;
        tmp = new int [n];

        return  merge(nums,0,n-1);

    }
    public int merge(int [] nums, int left, int right)
    {
        if(left>=right)
        {return 0;}



        int mid = (right+left)/2;

        int n1 =merge(nums,left,mid);
        int n2 =merge(nums,mid+1,right);
        int ret = n1+n2;

        int cur1 = left, cur2 = mid+1, i =left;
        // 升序
        while(cur2<= right)
        {
            while(cur1<= mid && nums[cur2]>= nums[cur1]/2) cur1++;
            if(cur1 > mid) break;

            ret += mid - cur1+1;
            cur2++;
        }

        while(cur1<=mid && cur2<=right)
        {
            tmp[i++] = nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        while(cur1<=mid) tmp[i++] = nums[cur1++];
        while(cur2<=right) tmp[i++] = nums[cur2++];

        for(int j = left; j<= right;j++)
        {
            nums[j] = tmp[j];
        }

        return ret;
    }

    public static void main(String[] args) {
        int [] nums = {
                1,3,2,3,1};
        Solution c = new Solution();
        int z = c.reversePairs(nums);
        System.out.println(z);
    }
}